A Beginner’s Guide to Mathematical Logic by Raymond M. Smullyan

Author:Raymond M. Smullyan
Language: eng
Format: epub, mobi
Publisher: Dover Publications, Inc.
Published: 2014-08-13T16:00:00+00:00

Also, in proving a formula of the form X ≡ Y, it reduces clutter to make two tableaux, one starting with T X followed by F Y, and the other starting with F X followed by T Y.

Exercise 1. Prove the following formulas using first-order tableaux:

(a) ∀x(∀y Py ⊃ Px)

(b) ∀x(P x ⊃ ∃x Px)

(c) ∼∃y Py ⊃ ∀y(∃x Px ⊃Py)

(d) ∃x Px ⊃ ∃y Py

(e) (∀x Px ∧ ∀x Qx) ≡ ∀x(Px ∧ Qx)

(f) (∀x Px ∨ ∀x Qx) ⊃ ∀x(Px ∨ Qx)

(g) ∃x(Px ∨ Qx) ≡ (∃x Px ∨ ∃x Qx)

(h) ∃x(Px ∧ Qx) ⊃ (∃x Px ∧ ∃x Qx)

Problem 1. The converse of (f) in the above exercise, i.e. the formula ∀x(Px ∨ Qx) ⊃ (∀x Px ∨ ∀x Qx), is not valid. Why? Also, the converse of (h) in the above exercise is not valid. Why?

Exercise 2. In this group of formulas to be proved by the tableau method, C is any closed formula (and thus for any parameter a, the formula C(a) is simply C).

(a) ∀x(Px ∨ C) ≡ (∀x Px ∨ C)

(b) ∃x(Px ∧ C) ≡ (∃x Px ∧ C)

(c) ∃xC ≡ C

(d) ∀xC ≡ C

(e) ∃x(C ⊃ Px) ≡ (C ⊃ ∃x Px)

(f) ∃x(Px ⊃ C) ≡ (∀x Px ⊃ C)

(g) ∀x(C ⊃ Px) ≡ (C ⊃ ∀x Px)

(h) ∀x(Px ⊃ C) ≡ (∃x Px ⊃ C)

(i) ∀x(Px ≡ C) ⊃ (∀x Px ∨ ∀x∼Px)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.